# 一个有序列表的顺序搜索

def orderSequetialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1
    return found

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1  # 二分法查找，列表下标的取首位和末尾二分之一位置的元素与要找的元素进行比较判断，如果恰好相等就返回找到，如果元素值小于要找的元素值，则将末尾的下标索引变更为前二分之一位置的索引-1，即将元素比对范围向左减小一半，如果元素值大于要找的元素值，则将首位的下标索引变更为前二分之一的位置的索引，即将元素的比对范围向右减小一半
    return found


if __name__ == "__main__":
    testlist = [0,1,2,9,13,19,20,43,90]
    print(orderSequetialSearch(testlist,3))
    print(orderSequetialSearch(testlist, 13))

    print(binarySearch(testlist, 3))
    print(binarySearch(testlist, 13))
